#include<iostream>
#include<vector>
using namespace std;
// template<class  con>
// void put_val(const con& val)
// {
//      con::const_iterator hehe = val.begin();//需要告诉编译器这个只是一个类型并不用太过在意，等它实例化了在进行寻找就行
//      //其实日常使用还是可以的但是就是当你要在作用域中需找某样东西的时候，就需要加上typename
//     for(auto i : val)
//     {
//         cout << val.size();
//         cout << i << endl;
//     }
// }
// int main()
// {
//     vector<int> arr = {1,2,3,4};
//     put_val(arr);
//     return 0;
// }

namespace yxt
{
    template<class T>
    struct Less
    {
        bool operator()(const T& n1,const T& n2)
        {
            return n1 < n2;
        }
    };
    template<class T>
    struct Grater
    {
        bool operator()(const T& n1,const T& n2)
        {
            return n1 > n2;
        }
    };
    //可以将传入比较方法进行确定是大堆还是小堆，就是进行仿函数方法进行比较
    //不支持遍历
    template<class T,class Contrianer = vector<T>,class Compare = Less<T>>//仿函数
    class priority_queue
    {
        Contrianer _queue;
    public:
        priority_queue(){}
        void adjust(size_t i)
        {
            //记录当前父节点的位置还有孩子节点的位置
            //要判断孩子节点的位置，如果合法就是进行判断
            //而且是要符合某个特征所以要选出孩子之中最符合特征的所以要进行假设进行比较
            size_t parents = i;
            size_t child = 2 * i + 1;
           
            //因为是从上往下进行相应的交换，所以要一层一层的父子进行交换
            while(child < _queue.size())
            {
                 if(Compare()(_queue[child] , _queue[child + 1]) && child + 1 < _queue.size())//万一右孩子不合法怎么办
                {
                    child++;
                }
                if(Compare()(_queue[parents],  _queue[child]))
                swap(_queue[parents],_queue[child]);
                else{
                    break;
                }
                parents = child;
                child = child * 2 + 1;
            }

        }
        void upjust(int _pos)
        {
            int child = _pos;
            int parents = (_pos - 1) / 2;
            //当孩子节点是根节点的时候就要停止
            while(child > 0)
            {
                if(Compare()(_queue[parents], _queue[child]))
                {
                    swap(_queue[child] ,_queue[parents]);
                }
                else{
                    break;
                }
                child = parents;
                parents = (child - 1) / 2;
            }
        }
        template<class Inputiterator>
        priority_queue(Inputiterator first,Inputiterator last)
        {
            //先将序列压入
            while(first != last)
            {
                _queue.push_back(*first);
                first++;
            }
            //进行建堆，因为是从子树的倒数第二层的子树开始向下建堆
            //所以我们要从最后的节点的父节点进行遍历
            //所以先得到pos然后进行访问，*2 + 1
            for(int i = (_queue.size() - 1 - 1) / 2;i >= 0;i--)
            {
                adjust(i);
            }
        }
        void push(const T& val)
        {
            //要放到叶子节点将进行向上调整
            _queue.push_back(val);
            //向上调整
            upjust(_queue.size() - 1);
        }
        void pop()
        {
            swap(_queue[0],_queue[_queue.size() - 1]);
            _queue.erase(_queue.end() - 1);
            for(int i = 0;i < _queue.size();i++)
            {
                adjust(i);
            }
        }
        size_t size()
        {
            return _queue.size();
        }
        T& top()
        {
            return _queue[0];
        }
        bool empty()
        {
            return _queue.empty();
        }
    };
}
int main()
{
    yxt::priority_queue<int> arr;
    arr.push(3);
    arr.push(4);
    arr.push(6);
    arr.push(5);
    arr.push(2);
    arr.push(9);
    while(!arr.empty())
    {
        cout << arr.top() << ' ';
        arr.pop(); 
    }
    
    return 0;
}
